package leetcode.L437;

/**
 * Definition for a binary tree node.
 * public class leetcode.L994.leetcode.TreeNode {
 *     int val;
 *     leetcode.L994.leetcode.TreeNode left;
 *     leetcode.L994.leetcode.TreeNode right;
 *     leetcode.L994.leetcode.TreeNode() {}
 *     leetcode.L994.leetcode.TreeNode(int val) { this.val = val; }
 *     leetcode.L994.leetcode.TreeNode(int val, leetcode.L994.leetcode.TreeNode left, leetcode.L994.leetcode.TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int pathSum(TreeNode root, int targetSum) {
        //对于每个节点向下(左子或者右子)遍历
        if (root == null) {
            return 0;
        }
        int ret = rootSum(root, targetSum);//作为根遍历
        ret += pathSum(root.left, targetSum);
        ret += pathSum(root.right, targetSum);
        return ret;
    }

    private int rootSum(TreeNode node, long resVal) {
        int ret=0;
        if (node == null) {
            return 0;
        }
        //对单个节点也需要特别判断，因为有可能恰好等于targetSum
        if (node.val == resVal) {
            ret++;
        }
        //然后将左子作为根，右子作为根去遍历
        ret += rootSum(node.left, resVal - node.val);
        ret += rootSum(node.right, resVal - node.val);
        return ret;
    }
}